#include <iostream>
#include <array>
//-----------------------------------------------------------
// class
// brief:存储方式：接邻表
//       有向图
//       出度表
//-----------------------------------------------------------
template<typename T, int VMAX = 100>
class Graph
{
public:
    struct node
    {
        unsigned long int id {};
        int index{};
        node* next {nullptr};
    };

    struct vertex
    {
        friend Graph;
    public:
        unsigned long int id {};    // 顶点标识
        T data;                     // 数据

    private:
        int   index{};              // 数组中的索引
        bool  visit{};              // 遍历标志
        node *next {nullptr};       // 指向下个顶点
    };

public:
    Graph(){}
    ~Graph()
    {

    }

    bool add_vertex(vertex &v)
    {
        if (l_vernum_ >= 100 || -1 != find_vertex(v.id))
        {
            return false;
        }
        l_vertex_[l_vernum_].id = v.id;
        l_vertex_[l_vernum_].index = l_vernum_;
        l_vertex_[l_vernum_].next = nullptr;
        l_vertex_[l_vernum_].data = v.data;
        l_vernum_++;
        return true;
    }

    bool add_edge(unsigned long int from_id, unsigned long int to_id)
    {
        int from_index = find_vertex(from_id);
        int to_index   = find_vertex(to_id);
        if (-1 == from_index || -1 == to_index)
        {
            return false;
        }
        node *n = new node;
        n->id = l_vertex_[to_index].id;
        n->index = l_vertex_[to_index].index;
        n->next = nullptr;

        if (!l_vertex_[from_index].next)
        {
            l_vertex_[from_index].next = n;
        }
        else
        {
            node* temp = l_vertex_[from_index].next;
            while (temp->next)
            {
                temp = temp->next;
            }
            temp->next = n;
        }
        return true;
    }

    bool remove_edge(vertex &from_v, vertex &to_v)
    {
        int from_index = find_vertex(from_v.id);
        int to_index   = find_vertex(to_v.id);
        if (-1 == from_index || -1 == to_index)
        {
            return false;
        }

        node* n = l_vertex_[from_index].next;
        if (n && n->index == to_index)
        {
            delete l_vertex_[from_index].next;
            l_vertex_[from_index].next = nullptr;
            return true;
        }

        while (n && n->next && n->next->index != to_index)
        {
            n = n->next;
        }

        if (n->next && n->next->index == to_index)
        {
            delete n->next;
            n->next = nullptr;
            return true;
        }
        return false;
    }

    bool exit_edge(vertex &from_v, vertex &to_v)
    {
        int from_index = find_vertex(from_v.id);
        int to_index   = find_vertex(to_v.id);
        if (-1 == from_index || -1 == to_index)
        {
            return false;
        }

        node* n = l_vertex_[from_index].next;
        if (n && n->index == to_index)
        {
            return true;
        }

        while (n && n->next && n->next->index != to_index)
        {
            n = n->next;
        }

        if (n->next && n->next->index == to_index)
        {
            return true;
        }
        return false;
    }

    bool add_edge(vertex &from_v, vertex &to_v)
    {
        add_vertex(from_v);
        add_vertex(to_v);
        return add_edge(from_v.id, to_v.id);
    }

    void DFS(vertex *v)
    {
        if (!v) return;

        if (v->visit)
        {
            // print circle:至少打印出来一条完整的链路
            std::cout << "circle id: ";
            std::cout << path_[0];
            path_[path_index++] = v->id;
            for (int i = 1; i < path_index; i++)
            {
                std::cout << "-->" << path_[i];
            }
            path_index--;
            std::cout << std::endl;
            return;
        }
        else
        {
            v->visit = true;
            path_[path_index++] = v->id;
            node *n = v->next;
            while (n)
            {
                DFS(&l_vertex_[n->index]);
                n = n->next;
            }
            path_index--;
        }
    }

    void traverse()
    {
        for (int i = 0; i < l_vernum_; i++)
        {
            l_vertex_[i].visit = false;
        }

        for (int i = 0; i < l_vernum_; i++)
        {
            if (l_vertex_[i].visit)
            {
                continue;
            }
            std::cout << i << " :" << std::endl;
            path_index = 0;
            DFS(&l_vertex_[i]);
        }
    }
    // 打印vertex的存储结构
    void test()
    {
        for (int i = 0; i < l_vernum_; i++)
        {
            std::cout << "vertex:id:" << l_vertex_[i].id << " index:" << l_vertex_[i].index << "  :";
            node *n = l_vertex_[i].next;
            while (n)
            {
                std::cout << "-->" << n->id << "-" << n->index;
                n = n->next;
            }
            std::cout << std::endl;
        }
    }

    void print_thread_mutex()
    {
        for (int i = 0; i < l_vernum_; i++)
        {
            std::cout << "vertex:id:" << l_vertex_[i].id << " thread id:" << l_vertex_[i].data.thread_id << " mutex:" << l_vertex_[i].data.mutex_add << " " << std::endl;
        }
    }

private:
    // 查找id为id的顶点，存在返回其索引，不存在返回-1
    int find_vertex(unsigned long int id)
    {
        for (int i = 0; i < l_vernum_; i++)
        {
            if (id == l_vertex_[i].id)
            {
                return i;
            }
        }
        return -1;
    }

private:
    std::array<vertex, VMAX>    l_vertex_{};
    int                         l_vernum_{};

    std::array<unsigned long int, VMAX> path_{};
    int                                 path_index{};
};




// int main()
// {


//     Graph<int> g;

//     Graph<int>::vertex v1;
//     v1.id = 1;
//     Graph<int>::vertex v2;
//     v2.id = 2;
//     Graph<int>::vertex v3;
//     v3.id = 3;
//     Graph<int>::vertex v4;
//     v4.id = 4;
//     Graph<int>::vertex v5;
//     v5.id = 5;

//     g.add_vertex(v1);
//     g.add_vertex(v2);
//     g.add_vertex(v3);
//     g.add_vertex(v4);
//     g.add_vertex(v5);

//     g.add_edge(1, 2);
//     g.add_edge(2, 1);
//     g.add_edge(2, 3);
//     g.add_edge(3, 5);
//     g.add_edge(5, 1);
//     g.add_edge(2, 4);
//     g.add_edge(4, 5);
//     g.add_edge(5, 4);

//     g.traverse();
//     return 0;
// }



